#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int getMoneyAmount(int n) {
        vector<vector<int>> memo(n + 1, vector<int>(n + 1));
        return dfs(1, n, memo);
    }
    int dfs(int left, int right, vector<vector<int>>& memo)
    {
        if (left >= right) return 0;
        if (memo[left][right]) return memo[left][right];
        int m = INT_MAX;
        for (int i = left; i <= right; i++)
            m = min(m, max(dfs(left, i - 1, memo), dfs(i + 1, right, memo)) + i);
        memo[left][right] = m;
        return m;
    }
};